/* https://notabug.org/dm9pZCAq/linked-list */
#ifndef LINKED_LIST_H
#define LINKED_LIST_H 1

#include <metalang99.h>

/* translate variable name to variable in "`ll` namespace" */
#define _LL_NAME(NAME) _ll_##NAME##__

/*
 * // define linked list
 * LL_DEF(node, int x, float y);
 *
 * // will be
 * typedef struct ... {
 *   int x;
 *   float y;
 *
 *   ...
 * } node;
 *
 * // to see actual code use preprocessor `${CC} -P -E | clang-format`
 */
#define LL_DEF(NAME, ...)                                                     \
	ML99_EVAL(ML99_typedef(                                               \
	    v(NAME),                                                          \
	    ML99_struct(v(_LL_NAME(NAME)),                                    \
			ML99_variadicsForEach(                                \
			    v(ML99_semicoloned),                              \
			    v(__VA_ARGS__,                                    \
			      struct _LL_NAME(NAME) * _LL_NAME(next))))))     \
	ML99_TRAILING_SEMICOLON()

/* get next element */
#define LL_NEXT(HEAD) ((HEAD)->_LL_NAME(next))

/* get last element */
#define LL_LAST(HEAD, LAST)                                                   \
	do {                                                                  \
		(LAST) = (HEAD);                                              \
		while (!!LL_NEXT(LAST))                                       \
			(LAST) = LL_NEXT(LAST);                               \
	} while (0)

#define LL_APPEND(HEAD, NEW)                                                  \
	do {                                                                  \
		if (!!(HEAD)) {                                               \
			__typeof__((HEAD)) _LL_NAME(tmp);                     \
			LL_LAST(HEAD, _LL_NAME(tmp));                         \
			LL_NEXT(_LL_NAME(tmp)) = (NEW);                       \
		} else {                                                      \
			(HEAD) = (NEW);                                       \
		}                                                             \
	} while (0)

#define LL_PREPEND(HEAD, NEW)                                                 \
	do {                                                                  \
		if (!!(HEAD)) LL_NEXT(NEW) = (HEAD);                          \
		(HEAD) = (NEW);                                               \
	} while (0)

#define LL_FOREACH(HEAD, ITEM)                                                \
	(ITEM) = (HEAD);                                                      \
	for (__typeof__((HEAD)) _LL_NAME(tmp) = LL_NEXT(ITEM); (ITEM);        \
	     (ITEM)			      = _LL_NAME(tmp),                \
				_LL_NAME(tmp) = (ITEM) ? LL_NEXT(ITEM)        \
						       : NULL)

/* get length */
#define LL_LENGTH(HEAD, LEN)                                                  \
	do {                                                                  \
		(LEN) = 0;                                                    \
		__typeof__((HEAD)) _LL_NAME(i);                               \
		LL_FOREACH(HEAD, _LL_NAME(i)) { (LEN)++; }                    \
	} while (0)

#define LL_REVERSE(HEAD)                                                      \
	do {                                                                  \
		__typeof__((HEAD)) _LL_NAME(item) = (HEAD),                   \
				   _LL_NAME(prev) = NULL;                     \
		while (!!_LL_NAME(item)) {                                    \
			__typeof__((HEAD)) _LL_NAME(next) =                   \
			    LL_NEXT(_LL_NAME(item));                          \
			LL_NEXT(_LL_NAME(item)) = _LL_NAME(prev);             \
			_LL_NAME(prev)		= _LL_NAME(item);             \
			_LL_NAME(item)		= _LL_NAME(next);             \
		}                                                             \
		(HEAD) = _LL_NAME(prev);                                      \
	} while (0)

#define LL_CONCAT(A, B)                                                       \
	do {                                                                  \
		if (!!(A)) {                                                  \
			__typeof__((A)) _LL_NAME(last) = (A);                 \
			LL_LAST((A), _LL_NAME(last));                         \
			LL_NEXT(_LL_NAME(last)) = (B);                        \
		} else {                                                      \
			(A) = (B);                                            \
		}                                                             \
	} while (0)

#define LL_SEARCH(HEAD, CMP, QUERY, FOUND)                                    \
	do {                                                                  \
		__typeof__((HEAD)) _LL_NAME(i);                               \
		LL_FOREACH((HEAD), _LL_NAME(i))                               \
		{                                                             \
			if (!((CMP)(_LL_NAME(i), (QUERY)))) break;            \
		}                                                             \
		(FOUND) = _LL_NAME(i);                                        \
	} while (0)

#define LL_DELETE(HEAD, ITEM)                                                 \
	do {                                                                  \
		if ((ITEM) == (HEAD)) {                                       \
			(HEAD) = LL_NEXT(HEAD);                               \
		} else {                                                      \
			__typeof__((HEAD)) _LL_NAME(cur) = (HEAD);            \
			while (LL_NEXT(_LL_NAME(cur))                         \
			       && LL_NEXT(_LL_NAME(cur)) != (ITEM))           \
				_LL_NAME(cur) = LL_NEXT(_LL_NAME(cur));       \
			LL_NEXT(_LL_NAME(cur)) = LL_NEXT(ITEM);               \
		}                                                             \
	} while (0)

#endif /* LINKED_LIST_H */
